'''
Module: eparser.py
Purpose: Implement the Earley parsing algorithm as described.
Author: Avishay Alon
'''
#########################################
### Imports
#########################################
import sys
import os
from collections import defaultdict

#########################################
### Globals
#########################################
USAGE = 'eparser.py <grammar filepath> <input filepath>'

#########################################
### Classes
#########################################
class Terminal(str):
    ''' Wrapper for distinguishing between terminal and non-terminal rules. '''
    pass

class Rule(object):
    ''' Contains head (str) and production (str).
        Assumes that a terminal rule will be initiated 
        with a production parameter of class Terminal. '''
    def __init__(self, head, production):
        self._head = head
        self._production = production
        self._is_terminal = isinstance(production, Terminal)

    def __str__(self):
        return 'Rule: %s -> %s, length: %d' % (
            self._head, 
            self._production, 
            len(self))

    def __len__(self):
        return len(self._production.split())

    def __eq__(self, other):
        return (self._head == other.head and 
                    self._production == other.production)
    def __ne__(self, other):
        return not (self == other)

    head = property(lambda self: self._head)
    production = property(lambda self: self._production)
    is_terminal = property(lambda self: self._is_terminal)

class Grammar(object):
    ''' This class is used to parse the grammar file, 
        process its various rules and symbols,
        and provide simple interface for use in the EarleyParser class. '''
    def __init__(self, grammar_file):
        self._rules = defaultdict(set)
        self._terminals = set()
        self._nonterminals = set()
        self._start_symbol = None
        self._load_from_file(grammar_file)
        self._rule_set = set()
        self._terminal_rules = set()

        for rule_set in self._rules.values():
            for rule in rule_set:
                self._rule_set.add(rule)

        for rule in self._rule_set:
            if isinstance(rule.production, Terminal):
                self._terminal_rules.add(rule)

        self._nonterminal_rules = self._rule_set.difference(self._terminal_rules)

    def _load_from_file(self, grammar_filepath):
        ''' This method loads a grammar file into the grammar object.
            Assumes normal form and specific formatting of HEAD -> BODY. 
            The head of the first rule is the start symbol. '''
        with open(grammar_filepath, 'rb') as grammar_file:
            rules = [ line.strip() for line in grammar_file.readlines() if line.strip() ]

        ### Process rules
        for rule in rules:
            head, body = [ element.strip() for element in rule.split('->') ]
            if not self._start_symbol:
                self._start_symbol = head
            self._nonterminals.add(head)
            ### Terminal rule
            if len(body.split()) == 1 and body.islower():
                self._terminals.add(body)
                self._rules[head].add(Rule(head, Terminal(body)))
            ### Non-terminal rule
            else:
                self._rules[head].add(Rule(head, body))

    def __str__(self):
        str_repr = '----------------------------------\n> Grammar:'
        for rule in self._rules[self._start_symbol]:
            str_repr = '%s\n%s' % (str_repr, rule, )
        for key, rule_set in self._rules.items():
            if key != self._start_symbol:
                for rule in rule_set:
                    str_repr = '%s\n%s' % (str_repr, rule, )
        str_repr = '%s\n----------------------------------' % (str_repr, )
        return str_repr

    terminals = property(lambda self: self._terminals)
    nonterminals = property(lambda self: self._nonterminals)
    rules = property(lambda self: self._rules)
    rule_set = property(lambda self: self._rule_set)
    start_symbol = property(lambda self: self._start_symbol)
    terminal_rules = property(lambda self: self._terminal_rules)
    nonterminal_rules = property(lambda self: self._nonterminal_rules)

class Edge(object):
    ''' The Edge object contains a Rule object and a dot index property. '''
    def __init__(self, rule, dot_index):
        self._rule = rule
        self._dot_index = dot_index
        self._is_active = dot_index < len(rule)

    def next_term(self):
        ''' Return the term/symbol following the dot index. '''
        return self._rule.production.split()[self._dot_index]

    def __str__(self):
        return '%s, dot_index = %d' % (self._rule, self._dot_index, )

    def __eq__(self, other):
        return (self._rule == other.rule and 
                    self._dot_index == other.dot_index)
    def __ne__(self, other):
        return not (self == other)

    production = property(lambda self: self._rule.production)
    active = property(lambda self: self._is_active)
    rule = property(lambda self: self._rule)
    dot_index = property(lambda self: self._dot_index)

class EarleyParser(object):
    ''' This class contains all the logic of the Earley parsing algorithm. 
        Assumes the grammar given is of class Grammar. '''
    def __init__(self, grammar):
        ''' Initialization method. must provide grammar. '''
        self._chart = None
        self._grammar = grammar

    def _get_all_edges(self):
        ''' Scans the chart and returns all the existing edges. '''
        edges = set()
        for i in self._chart.keys():
            for j in self._chart.keys():
                for edge in self._chart[i][j]:
                    edges.add(edge)
        return edges

    def _get_rightsisters(self, edge):
        ''' Given an active edge A -> x*By, 
            create and return edges for rules B -> *z '''
        if not edge.active or edge.rule.is_terminal:
            return []
        term = edge.next_term()
        if term not in self._grammar.nonterminals:
            return []
        return [ Edge(rule, 0) for rule in self._grammar.rule_set if rule.head == term ]

    def _get_leftsisters(self, edge):
        ''' Given an inactive/complete edge B -> z*, 
            return all existing edges A -> x*By '''
        if edge.active:
            return []
        return [ leftsister for leftsister in self._get_all_edges()
                    if leftsister.active and
                    leftsister.next_term() == edge.rule.head ]

    def _enteredge(self, i, edge, j):
        ''' Recursively perform predictions and completions on edges. '''
        if edge in self._chart[i][j]:
            return
        self._chart[i][j].append(edge)
        ## Predict
        if edge.active:
            for rightsister in self._get_rightsisters(edge):
                self._enteredge(j, rightsister, j)
        ## Complete
        else:
            for leftsister in self._get_leftsisters(edge):
                for k in [ index for index in self._chart.keys() 
                            if leftsister in self._chart[index][i] ]:
                    combined = Edge(leftsister.rule, leftsister.dot_index + 1)
                    self._enteredge(k, combined, j)

    def _init_chart(self, length):
        ''' Initialize the chart: chart[i][j] = list of edges. '''
        self._chart = {}
        for index in range(length + 1):
            self._chart[index] = defaultdict(list)

    def parse(self, words):
        ''' The parse method returns True if the input given is parsable 
            from the grammar given, and False otherwise. '''
        self._init_chart(len(words))
        ## Add the start rule
        start_rule = Rule("S'", self._grammar.start_symbol)
        self._enteredge(0, Edge(start_rule, 0), 0)
        ## Scan the input words
        for j in range(len(words)):
            for rule in self._grammar.terminal_rules:
                if words[j] == rule.production:
                    self._enteredge(j, Edge(rule, 1), j + 1)
        ## Is the final edge found in [0][n]?
        return Edge(start_rule, 1) in self._chart[0][len(words)]

#########################################
### Functions
#########################################
def main(args):
    ''' Main function:
        1. Validates inpurt
        2. Creates a grammar and an Earley parser
        3. Parses the input according to the grammar and outputs the result. '''
    grammar_filepath, input_filepath = args
    incorrect_paths = [ path for path in args if not os.path.isfile(path) ]
    if incorrect_paths:
        raise ValueError('Incorrect file paths %s' % incorrect_paths)

    with open(input_filepath, 'rb') as input_file:
        input_lines = [ line.strip() for line in input_file.readlines() if line.strip() ]

    grammar = Grammar(grammar_filepath)
    print grammar
    earley_parser = EarleyParser(grammar)

    for line in input_lines:
        result = earley_parser.parse(line.split())
        print line, ':', result

if __name__ == '__main__':
    if len(sys.argv) == 3:
        main(sys.argv[1:])
    else:
        print USAGE